This invention deals with quantum computers. A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating these qubits. Quantum computers with only a few bits have already been built. For a review of quantum computers, see DiV95: D. P. DiVincenzo, Science 270, 255 (1995). See also Ste97:A. M. Steane, Los Alamos eprint http://xxx.lanl.gov/abs/quant-ph/9708022  www.arxiv.org/abs/quant-ph/9708022.
This invention also deals with Quantum Bayesian (QB) nets. QB Nets are a method of modeling quantum systems graphically in terms of network diagrams. For more information, see Tuc95: R. R. Tucci, Int. Jour. of Mod. Physics B9, 295 (1995). See also Tuc98: U.S. Pat. No. 5,787,236.
In classical computation and digital electronics, one deals with sequences of elementary instructions (instructions such as AND, NOT and OR). These sequences are used to manipulate an array of classical bits. The instructions are elementary in the sense that they act on only a few bits (usually 1, 2 or 3) at a time. Henceforth, we will sometimes refer to sequences as products and to instructions as operations, operators, steps or gates. Furthermore, we will abbreviate the phrase “sequence of elementary operations” by “SEO”. In quantum computation, one also deals with SEOs, but for manipulating qubits instead of classical bits.
This invention comprises a classical computer running a computer program that expresses the information contained in a QB net as a SEO. One can then run these SEOs on a quantum computer. Of course, QB nets can and have been run entirely on a classical computer. (See the software program called “Quantum Fog”, produced by the Artiste company (www.ar-tiste.com)). However, because of the higher speeds promised by quantum parallelism, one expects QB nets to run much faster on a quantum computer.
With classical computers, one usually writes a computer program in a high level language (like Fortran, C or C++). A compiler then expresses this as a SEO for manipulating bits. In the case of quantum computers, a QB net may be thought of as a program in a high level language. This invention is like a “quantum compiler” in the sense that it can take a QB net input, and re-express it as a SEO that can then be used to manipulate qubits.
This invention shows how to reduce a QB net into a SEO by a two step process. First, express the information contained in the QB net as a sequence of unitary operators. Second, express each of those unitary operators as a SEO. An appendix to this document contains the C++ source code of a computer program called “Qubiter.1.0”. In its current version (1.0), Qubiter can decompose into a SEO only the simplest non-trivial kind of QB net: a single unitary matrix, or, equivalently, 2 connected nodes. Future versions of Qubiter are planned that will take an arbitrary QB net as input, and return as output a SEO for running a quantum computer.
QB nets are to quantum physics what Classical Bayesian (CB) nets are to classical physics. For a review of CB nets, see Nea9O: Richard E. Neapolitan, Probabilistic Reasoning in Expert Systems: Theory and Algorithms (Wiley, 1990). See also Pea88: Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kaufmann, Palo Alto, 1988). CB nets have been used very successfully in the field of artificial intelligence (AI). Thus, we hope and expect that some day QB nets, running on quantum computers, will be used for AI applications. In fact, we believe that quantum computers are ideally suited for such applications. First, because AI tasks often require tremendous power, and quantum computers seem to promise this. Second, because quantum computers are plagued by quantum noise, which makes their coherence times short. There are palliatives to this, such as quantum error correction (See the review Ste97). But such palliatives come at a price: a large increase in the number of steps. The current literature often mentions factoring a large number into primes as a future use of quantum computers (See the review Ste97). However, due to noise, quantum computers may ultimately prove to be impractical for doing long precise calculations such as this. On the other hand, short coherence times appear to be a less serious problem for the types of calculations involved in AI. The human brain has coherence times too short to factor a 100 digit number into primes, and yet long enough to conceive the frescoes in the Sistine Chapel. We do not mean to imply that the human brain is a quantum computer. An airplane is not a bird, but it makes a good flyer. Perhaps a quantum computer, although not a human brain, can make a good thinker.
To our knowledge, nobody else has invented a method of reducing an arbitrary QB net to a SEO for running a quantum computer. It's true that previous workers (See Bar95: A. Barrenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. H. Smolin, H. Weinfurter, Physical Review A 52, 3457 (1995)) have described a method for reducing a single unitary operator into a SEO. But our method for doing this is significantly different from theirs. Their method is based on a mathematical technique described in Rec94: M. Reck and A. Zeilinger, Physical Review Letters 73, 58 (1994). Our method is based on a mathematical technique called the CS Decomposition, to be described later. For a review of the CS decomposition, see Pai94: C. C. Paige, M. Wei, Linear Algebra And Its Applications 208, 303 (1994). Our CS method for reducing unitary matrices has inherent binary symmetries that make it easy to apply to qubit systems, which also possess binary symmetries. The method of Bar95 possesses no such symmetries. For this reason, we believe our method to be superior to theirs.